package com.sfx.算法专题.滑动窗口.固定窗口;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-08-07
 * Time: 15:38
 */
public class Code_6_findAnagrams {
    static class Solution {
        public List<Integer> findAnagrams(String ss, String pp) {
            char[] s = ss.toCharArray();
            char[] p = pp.toCharArray();
            List<Integer> res = new ArrayList<>();
            int left = 0;
            int right = 0;
            int[] hash1 = new int[128];
            int[] hash2 = new int[128];
            for(int i =0;i<p.length;++i) {
                hash1[p[i]] ++;
            }
            while(right < s.length) {
                hash2[s[right]] ++;
                if((right-left+1) > p.length) {
                    hash2[s[left]]--;
                    left++;
                }else if((right-left+1) == p.length) {
                    int i = 0;
                    for(i =left;i<right;++i) {
                        if(hash1[s[i]] != hash2[s[i]]) {
                            break;
                        }
                    }
                    if(i == right)
                        res.add(left);
                }
                right ++;
            }
            return res;
        }
    }

    static class Solution1 {
        public List<Integer> findAnagrams(String ss, String pp) {
            char[] s = ss.toCharArray();
            char[] p = pp.toCharArray();
            List<Integer> res = new ArrayList<>();
            int left = 0;
            int right = 0;
            int[] hash1 = new int[128];
            int[] hash2 = new int[128];
            for(int i =0;i<p.length;++i) {
                hash1[p[i]] ++;
            }
            //使用一个变量维护有效个数的个数
            //出窗口和进窗口都要进行判断看是否需要更新cnt
            int cnt = 0;
            while(right < s.length) {
                //进窗口前判断
                if(hash2[s[right]] < hash1[s[right]]) {
                    cnt ++;
                }
                hash2[s[right]] ++;
                if((right-left + 1) > p.length) {
                    hash2[s[left]]--;
                    //出窗口后
                    if(hash2[s[left]] < hash1[s[left]]) {
                        cnt--;
                    }
                    left++;
                }
                if(cnt == p.length) res.add(left);
                right++;
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.findAnagrams("abab","ab");
    }
}
